//
// Created by Semir on 2020/5/24.
//

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>

using namespace std;

int GetRandom(int min, int max) {
    srand(time(nullptr));
    return rand() % (abs(max - min) + 1) + min;
}

void Swap(vector<int>& arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

int Partition(vector<int>& arr, int low, int high) {
    if (low > high) {
        return high;
    }
    int index = GetRandom(low, high);
    Swap(arr, index, high);
    int i = low;
    int j = low;
    while (j < high) {
        if (arr[j] < arr[high]) {
            if (i != j) {
                Swap(arr, i, j);
            }
            i++;
        }
        j++;
    }
    Swap(arr, i, high);
    return i;
}

vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
    vector<int> res;
    if (input.empty() || k <= 0 || k > input.size()) {
        return res;
    }
    int low = 0;
    int high = input.size() - 1;
    int index = Partition(input, low, high);
    while (index < k - 1 || index > k) {
        if (index < k) {
            low = index + 1;
        } else {
            high = index - 1;
        }
        index = Partition(input, low, high);
    }
    for (int i = 0; i < k; i++) {
        res.emplace_back(input[i]);
    }
    return res;
}

int main() {
    vector<int> input = {4,5,1,6,2,7,3,8};
    vector<int> res = GetLeastNumbers_Solution(input, 4);
    cout << res.size() << endl;
    return 0;
}